1048. 最长字符串链【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DP + 哈希表

1. 📝 题目描述

• leetcode

给出一个单词数组 words，其中每个单词都由小写英文字母组成。

如果我们可以 不改变其他字符的顺序，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB，那么我们认为 wordA 是 wordB 的 前身。

• 例如，"abc" 是 "abac" 的 前身，而 "cba" 不是 "bcad" 的 前身

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链。

从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度。

---

示例 1：

输入：words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]

示例 2：

输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出：5
解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

示例 3：

输入：words = ["abcd","dbqca"]
输出：1
解释：字链["abcd"]是最长的字链之一。
["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。

---

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] 仅由小写英文字母组成。

2. 🎯 s.1 - DP + 哈希表

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {string[]} words
 * @return {number}
 */
var longestStrChain = function (words) {
  words.sort((a, b) => a.length - b.length)
  const dp = new Map()
  let res = 1
  for (const word of words) {
    let best = 1
    for (let i = 0; i < word.length; i++) {
      const prev = word.slice(0, i) + word.slice(i + 1)
      if (dp.has(prev)) {
        best = Math.max(best, dp.get(prev) + 1)
      }
    }
    dp.set(word, best)
    res = Math.max(res, best)
  }
  return res
}

• 时间复杂度：$O(n\cdot L^2)$，其中 $n$ 是单词数量，$L$ 是单词最大长度
• 空间复杂度：$O(n\cdot L)$，哈希表存储

算法思路：

• 按单词长度排序，用哈希表存储每个单词的最长链长度
• 对于每个单词，尝试删除每个位置的字符，检查前身是否在哈希表中
• 更新当前单词的链长度为所有前身中的最大值 + 1